/**
 * @file   Dynamic.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Wed Dec 30 13:57:43 2020
 * 
 * @brief  functions
 * 
 * 
 */

#include <iostream>

int length(char _a[]) {
    int len = 0;
    while (_a[len]!=0) {
	len++;
    }
    
    return len;
}

void longest(char _a[], char _b[]) {
    int b_len = length(_b);
    int a_len = length(_a);
    
    int c_list[b_len+1][a_len+1];
    char b_list[b_len+1][a_len+1];
    for (int i=0;i<b_len+1;i++) {
	c_list[i][0] = 0;
    }
    for (int j=0;j<a_len+1;j++) {
	c_list[0][j] = 0;
    }

    for (int i=1;i<b_len+1;i++) {
	for (int j=1;j<a_len+1;j++) {
	    if (_a[j-1]==_b[i-1]) {
		b_list[j][i] = '\\';
		c_list[j][i] = c_list[j-1][i-1] + 1;
	    } else if (c_list[j-1][i]>=c_list[j][i-1]) {
		b_list[j][i] = '|';
		c_list[j][i] = c_list[j-1][i];
	    } else {
		b_list[j][i] = '-';
		c_list[j][i] = c_list[j][i-1];
	    }
	}
    }

    int i = a_len;
    int j = b_len;
    int index = c_list[i][j];
    char result[index+1];
    result[index] = 0;
    
    while (i>0 && j>0) {
	if (b_list[i][j]=='\\') {
	    index--;
	    result[index] = _a[i-1];
	    i--;
	    j--;
	} else if (b_list[i][j]=='-') {
	    j--;
	} else {
	    i--;
	}
    }
    std::cout << result << std::endl;
    
/*
    for (int i=1;i<a_len+1;i++) {
	for (int j=1;j<b_len+1;j++) {
	    std::cout << b_list[i][j] << c_list[i][j] << "\t"; 
	}
	std::cout << std::endl;
    }
    std::cout << std::endl;
*/
}
